﻿//https://leetcode.cn/problems/maximum-total-reward-using-operations-i/
class Solution {
    bool vist[2001];
    int n;
    int memo[2001][4000];
public:
    int maxTotalReward(vector<int>& rewardValues)
    {
        n = rewardValues.size();
        sort(rewardValues.begin(), rewardValues.end());
        return dfs(rewardValues, 0, 0);
    }

    int dfs(vector<int>& rewardValues, int pos, int maxsum)
    {
        if (pos >= n) return maxsum;
        if (memo[pos][maxsum]) return memo[pos][maxsum];

        //选
        int ret1 = maxsum < rewardValues[pos] ? dfs(rewardValues, pos + 1, maxsum + rewardValues[pos]) : maxsum;
        //不选
        int ret2 = dfs(rewardValues, pos + 1, maxsum);
        int ret = max(ret1, ret2);
        memo[pos][maxsum] = ret;

        return ret;
    }
};